SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Regular tree grammar</title>

</head>

Regular tree grammar

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a> and <a href="Formal_language_theory" class="mw-redirect" title="Formal language theory">formal language theory</a>, a regular tree grammar is a <a href="Formal_grammar" title="Formal grammar">formal grammar</a> that describes a set of <a href="Tree_(graph_theory)" title="Tree (graph theory)">directed trees</a>, or <a href="Term_(logic)" title="Term (logic)">terms</a>.<a href="#cite_note-1">[1]</a> A <a href="Regular_grammar" title="Regular grammar">regular word grammar</a> can be seen as a special kind of regular tree grammar, describing a set of single-<a href="Path_(graph_theory)" title="Path (graph theory)">path</a> trees.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

A regular tree grammar G is defined by the tuple G = (N, Σ, Z, P), where:

<ul><li>N is a finite set of nonterminals,</li>

<li>Σ is a <a href="Ranked_alphabet" title="Ranked alphabet">ranked alphabet</a> (i.e., an alphabet whose symbols have an associated <a href="Arity" title="Arity">arity</a>) disjoint from N,</li>

<li>Z is the starting nonterminal, with Z ∈ N, and</li>

<li>P is a finite set of productions of the form A → t, with A ∈ N, and t ∈ TΣ(N), where TΣ(N) is the associated <a href="Term_algebra" title="Term algebra">term algebra</a>, i.e. the set of all trees composed from symbols in Σ ∪ N according to their arities, where nonterminals are considered nullary.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Derivation_of_trees">Derivation of trees</h2></div>

The grammar G implicitly defines a set of trees: any tree that can be derived from Z using the rule set P is said to be described by G.

This set of trees is known as the <a href="Formal_language" title="Formal language">language</a> of G.

Formally, the relation ⇒G on the set TΣ(N) is defined as follows:

A tree t1∈ TΣ(N) can be derived in a single step into a tree t2 ∈ TΣ(N)

(in short: t1 ⇒G t2), if there is a context S and a production (A→t) ∈ P such that:

Here, a context means a tree with exactly one hole in it; if S is such a context, S[t] denotes the result of filling the tree t into the hole of S.

The tree language generated by G is the language L(G) = { t ∈ TΣ | Z ⇒G* t }.

Here, TΣ denotes the set of all trees composed from symbols of Σ, while ⇒G* denotes successive applications of ⇒G.

A language generated by some regular tree grammar is called a regular <a href="Tree_language" class="mw-redirect" title="Tree language">tree language</a>.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

Let G1 = (N1,Σ1,Z1,P1), where

<ul><li>N1 = {Bool, BList } is our set of nonterminals,</li>

<li>Σ1 = { true, false, nil, cons(.,.) } is our ranked alphabet, arities indicated by dummy arguments (i.e. the symbol cons has arity 2),</li>

<li>Z1 = BList is our starting nonterminal, and</li>

<li>the set P1 consists of the following productions:

<ul><li>Bool → false</li>

<li>BList → nil</li>

<li>BList → cons(Bool,BList)</li></ul></li></ul>

An example derivation from the grammar G1 is

BList

⇒ cons(Bool,BList)

⇒ cons(false,cons(Bool,BList))

⇒ cons(false,cons(true,nil)).

The image shows the corresponding <a href="Derivation_tree" class="mw-redirect" title="Derivation tree">derivation tree</a>; it is a tree of trees (main picture), whereas a derivation tree in <a href="Regular_grammar" title="Regular grammar">word grammars</a> is a tree of strings (upper left table).

The tree language generated by G1 is the set of all finite lists of boolean values, that is, L(G1) happens to equal TΣ1.

The grammar G1 corresponds to the algebraic data type declarations (in the <a href="Standard_ML#Algebraic_datatypes" title="Standard ML">Standard ML</a> programming language):

<div class="mw-highlight mw-highlight-lang-sml mw-content-ltr" dir="ltr"><pre>datatype Bool

= false

| true

datatype BList

= nil

| cons of Bool * BList

</pre></div>

Every member of L(G1) corresponds to a Standard-ML value of type BList.

For another example, let G2 = (N1, Σ1, BList1, P1 ∪ P2), using the nonterminal set and the alphabet from above, but extending the production set by P2, consisting of the following productions:

<ul><li>BList1 → cons(true,BList)</li>

<li>BList1 → cons(false,BList1)</li></ul>

The language L(G2) is the set of all finite lists of boolean values that contain true at least once. The set L(G2) has no datatype counterpart in Standard ML, nor in any other functional language.

It is a proper subset of L(G1).

The above example term happens to be in L(G2), too, as the following derivation shows:

BList1

⇒ cons(false,BList1)

⇒ cons(false,cons(true,BList))

⇒ cons(false,cons(true,nil)).

<div class="mw-heading mw-heading2"><h2 id="Language_properties">Language properties</h2></div>

If L1, L2 both are regular tree languages, then the tree sets L1 ∩ L2, L1 ∪ L2, and L1 \ L2 are also regular tree languages, and it is decidable whether L1 ⊆ L2, and whether L1 = L2.

<div class="mw-heading mw-heading2"><h2 id="Alternative_characterizations_and_relation_to_other_formal_languages">Alternative characterizations and relation to other formal languages</h2></div>

<ul><li>Regular tree grammars are a generalization of <a href="Regular_grammar" title="Regular grammar">regular word grammars</a>.</li>

<li>The regular tree languages are also the languages recognized by bottom-up <a href="Tree_automaton" title="Tree automaton">tree automata</a> and nondeterministic top-down tree automata.<a href="#cite_note-Comon-2">[2]</a></li>

<li>Rajeev Alur and Parthasarathy Madhusudan related a subclass of regular binary tree languages to <a href="Nested_word" title="Nested word">nested words</a> and <a href="Visibly_pushdown_language" class="mw-redirect" title="Visibly pushdown language">visibly pushdown languages</a>.<a href="#cite_note-Alur2004-3">[3]</a><a href="#cite_note-Alur2009-4">[4]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Applications of regular tree grammars include:

<ul><li><a href="Code_generation_(compiler)#Major_tasks_in_code_generation" title="Code generation (compiler)">Instruction selection</a> in compiler code generation<a href="#cite_note-5">[5]</a></li>

<li>A <a href="Decision_procedure" class="mw-redirect" title="Decision procedure">decision procedure</a> for the <a href="First-order_logic" title="First-order logic">first-order logic</a> <a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">theory</a> of formulas over <a href="First-order_logic#Equality_and_its_axioms" title="First-order logic">equality</a> (=) and <a href="Set_(mathematics)#Membership" title="Set (mathematics)">set membership</a> (∈) as the only <a href="First-order_logic#Non-logical_symbols" title="First-order logic">predicates</a><a href="#cite_note-6">[6]</a></li>

<li>Solving <a href="Constraint_satisfaction_problem#Decision_problems" title="Constraint satisfaction problem">constraints</a> about mathematical sets<a href="#cite_note-7">[7]</a></li>

<li>The set of all truths expressible in first-order logic about a finite algebra (which is always a regular tree language)<a href="#cite_note-8">[8]</a></li>

<li>Graph-search <a href="#cite_note-9">[9]</a></li></ul>

<ul><li><a href="Set_constraint" title="Set constraint">Set constraint</a> – a generalization of regular tree grammars</li>

<li><a href="Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining grammar</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation citeseerx cs1">"Regular tree grammars as a formalism for scope underspecification". <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.5484">10.1.1.164.5484</a>.</cite>

</li>

<li id="cite_note-Comon-2"><a href="#cite_ref-Comon_2-0">^</a> <cite id="CITEREFComonDauchetGilleronLöding2007" class="citation web cs1">Comon, Hubert; Dauchet, Max; Gilleron, Remi; Löding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 October 2007). <a rel="nofollow" class="external text" href="http://www.grappa.univ-lille3.fr/tata">"Tree Automata Techniques and Applications"</a>. Retrieved 25 January 2016.</cite>

</li>

<li id="cite_note-Alur2004-3"><a href="#cite_ref-Alur2004_3-0">^</a> <cite id="CITEREFAlurMadhusudan2004" class="citation book cs1">Alur, R.; Madhusudan, P. (2004). <a rel="nofollow" class="external text" href="http://www.cis.upenn.edu/~alur/Stoc04.pdf">"Visibly pushdown languages"</a> (PDF). <a rel="nofollow" class="external text" href="https://repository.upenn.edu/cgi/viewcontent.cgi?article=1174&context=cis_papers">Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04</a>. pp. 202–211. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1007352.1007390">10.1145/1007352.1007390</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1581138528</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7473479">7473479</a>.</cite> Sect.4, Theorem 5,

</li>

<li id="cite_note-Alur2009-4"><a href="#cite_ref-Alur2009_4-0">^</a> <cite id="CITEREFAlurMadhusudan2009" class="citation journal cs1">Alur, R.; Madhusudan, P. (2009). <a rel="nofollow" class="external text" href="http://www.cis.upenn.edu/~alur/Jacm09.pdf">"Adding nesting structure to words"</a> (PDF). Journal of the ACM. 56 (3): 1–43. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.9971">10.1.1.145.9971</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1516512.1516518">10.1145/1516512.1516518</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:768006">768006</a>.</cite> Sect.7

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFEmmelmann1991" class="citation conference cs1">Emmelmann, Helmut (1991). "Code Selection by Regularly Controlled Term Rewriting". Code Generation - Concepts, Tools, Techniques. Workshops in Computing. Springer. pp. 3–29.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFComon1990" class="citation conference cs1">Comon, Hubert (1990). "Equational Formulas in Order-Sorted Algebras". Proc. ICALP.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFGilleronTisonTommasi1993" class="citation conference cs1">Gilleron, R.; Tison, S.; Tommasi, M. (1993). "Solving Systems of Set Constraints using Tree Automata". 10th Annual Symposium on Theoretical Aspects of Computer Science. LNCS. Vol. 665. Springer. pp. 505–514.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFBurghardt2002" class="citation conference cs1">Burghardt, Jochen (2002). "Axiomatization of Finite Algebras". Advances in Artificial Intelligence. LNAI. Vol. 2479. Springer. pp. 222–234. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1403.7347">1403.7347</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2014arXiv1403.7347B">2014arXiv1403.7347B</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-44185-9</bdi>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFZiv-Ukelson2016" class="citation conference cs1">Ziv-Ukelson, Smoly (2016). Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human–viral Infection Patterns. J. of Comp. Bio.</cite> <a rel="nofollow" class="external autonumber" href="https://www.liebertpub.com/doi/full/10.1089/cmb.2015.0168">[1]</a>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li>Regular tree grammars were already described in 1968 by:

<ul><li><cite id="CITEREFBrainerd1968" class="citation journal cs1">Brainerd, W.S. (1968). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0019-9958%2868%2990917-0">"The Minimalization of Tree Automata"</a>. Information and Control. 13 (5): 484–491. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0019-9958%2868%2990917-0">10.1016/s0019-9958(68)90917-0</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10945%2F40204">10945/40204</a>.</cite></li>

<li><cite id="CITEREFThatcherWright1968" class="citation journal cs1">Thatcher, J.W.; Wright, J.B. (1968). "Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic". Mathematical Systems Theory. 2 (1): 57–81. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01691346">10.1007/BF01691346</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:31513761">31513761</a>.</cite></li></ul></li>

<li>A book devoted to tree grammars is: <cite id="CITEREFNivatPodelski1992" class="citation book cs1">Nivat, Maurice; Podelski, Andreas (1992). Tree Automata and Languages. Studies in Computer Science and Artificial Intelligence. Vol. 10. North-Holland.</cite></li>

<li>Algorithms on regular tree grammars are discussed from an efficiency-oriented view in: <cite id="CITEREFAikenMurphy1991" class="citation conference cs1">Aiken, A.; Murphy, B. (1991). "Implementing Regular Tree Expressions". ACM Conference on Functional Programming Languages and Computer Architecture. pp. 427–447. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.3766">10.1.1.39.3766</a>.</cite></li>

<li>Given a mapping from trees to weights, <a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>'s generalization of <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's shortest-path algorithm</a> can be applied to a regular tree grammar to compute for each nonterminal the minimum weight of a derivable tree. Based on this information, it is straightforward to enumerate its language in increasing weight order. In particular, any nonterminal with infinite minimum weight produces the empty language. See: <cite id="CITEREFKnuth1977" class="citation journal cs1">Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2877%2990002-3">10.1016/0020-0190(77)90002-3</a>.</cite></li>

<li>Regular tree automata have been generalized to admit equality tests between sibling nodes in trees. See: <cite id="CITEREFBogaertTison1992" class="citation conference cs1">Bogaert, B.; Tison, Sophie (1992). "Equality and Disequality Constraints on Direct Subterms in Tree Automata". Proc. 9th STACS. LNCS. Vol. 577. Springer. pp. 161–172.</cite></li>

<li>Allowing equality tests between deeper nodes leads to undecidability. See: <cite id="CITEREFTommasi1991" class="citation book cs1">Tommasi, M. (1991). Automates d'Arbres avec Tests d'Égalités entre Cousins Germains. LIFL-IT.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Automata_theory:_formal_languages_and_formal_grammars385" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Automata_theory:_formal_languages_and_formal_grammars385" style="font-size:114%;margin:0 4em"><a href="Automata_theory" title="Automata theory">Automata theory</a>: <a href="Formal_language" title="Formal language">formal languages</a> and <a href="Formal_grammar" title="Formal grammar">formal grammars</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd plainlist" style="width:100%;padding:0;background:transparent;color:inherit;"><div style="padding:0px"><table class="navbox-columns-table" style="border-spacing: 0px; text-align:left;width:100%;"><tbody><tr><td class="navbox-abovebelow" style="font-weight:bold;"><a href="Chomsky_hierarchy" title="Chomsky hierarchy">Chomsky hierarchy</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="Formal_grammar" title="Formal grammar">Grammars</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="Formal_language" title="Formal language">Languages</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="Abstract_machine" title="Abstract machine">Abstract machines</a></td></tr><tr style="vertical-align:top"><td class="navbox-list" style="padding:0px;text-align: center;width:10em;"><div>

</div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div>

<ul><li><a href="Unrestricted_grammar" title="Unrestricted grammar">Unrestricted</a></li>

<li>(no common name)</li>

<li><a href="Context-sensitive_grammar" title="Context-sensitive grammar">Context-sensitive</a></li>

<li>Positive <a href="Range_concatenation_grammars" class="mw-redirect" title="Range concatenation grammars">range concatenation</a></li>

<li><a href="Indexed_grammar" title="Indexed grammar">Indexed</a></li>

<li><a href="Linear_context-free_rewriting_system" class="mw-redirect" title="Linear context-free rewriting system">Linear context-free rewriting systems</a></li>

<li><a href="Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining</a></li>

<li><a href="Context-free_grammar" title="Context-free grammar">Context-free</a></li>

<li><a href="Deterministic_context-free_grammar" title="Deterministic context-free grammar">Deterministic context-free</a></li>

<li><a href="Nested_word" title="Nested word">Visibly pushdown</a></li>

<li><a href="Regular_grammar" title="Regular grammar">Regular</a></li>

<li><a href="Non-recursive_grammar" class="mw-redirect" title="Non-recursive grammar">Non-recursive</a></li></ul>

</div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div>

<ul><li><a href="Recursively_enumerable_language" title="Recursively enumerable language">Recursively enumerable</a></li>

<li><a href="Recursive_language" title="Recursive language">Decidable</a></li>

<li><a href="Context-sensitive_language" title="Context-sensitive language">Context-sensitive</a></li>

<li>Positive <a href="Range_concatenation_language" class="mw-redirect" title="Range concatenation language">range concatenation</a>*</li>

<li><a href="Indexed_language" title="Indexed language">Indexed</a>*</li>

<li><a href="Linear_context-free_rewriting_language" class="mw-redirect" title="Linear context-free rewriting language">Linear context-free rewriting language</a></li>

<li><a href="Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining</a></li>

<li><a href="Context-free_language" title="Context-free language">Context-free</a></li>

<li><a href="Deterministic_context-free_language" title="Deterministic context-free language">Deterministic context-free</a></li>

<li><a href="Nested_word" title="Nested word">Visibly pushdown</a></li>

<li><a href="Regular_language" title="Regular language">Regular</a></li>

<li><a href="Finite_language" class="mw-redirect" title="Finite language">Finite</a></li></ul>

</div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div>

<ul><li><a href="Turing_machine" title="Turing machine">Turing machine</a></li>

<li><a href="Decider_(Turing_machine)" title="Decider (Turing machine)">Decider</a></li>

<li><a href="Linear_bounded_automaton" title="Linear bounded automaton">Linear-bounded</a></li>

<li><a href="PTIME" class="mw-redirect" title="PTIME">PTIME</a> Turing Machine</li>

<li><a href="Nested_stack_automaton" title="Nested stack automaton">Nested stack</a></li>

<li><a href="Thread_automaton" title="Thread automaton">Thread automaton</a></li>

<li>restricted <a href="Tree_stack_automaton" title="Tree stack automaton">Tree stack automaton</a></li>

<li><a href="Embedded_pushdown_automaton" title="Embedded pushdown automaton">Embedded pushdown</a></li>

<li><a href="Pushdown_automaton" title="Pushdown automaton">Nondeterministic pushdown</a></li>

<li><a href="Deterministic_pushdown_automaton" title="Deterministic pushdown automaton">Deterministic pushdown</a></li>

<li><a href="Nested_word" title="Nested word">Visibly pushdown</a></li>

<li><a href="Finite-state_machine" title="Finite-state machine">Finite</a></li>

<li><a href="Aperiodic_finite_state_automaton" class="mw-redirect" title="Aperiodic finite state automaton">Counter-free (with aperiodic finite monoid)</a></li>

<li><a href="Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Acyclic finite</a></li></ul>

</div></td></tr></tbody></table></div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>Each category of languages, except those marked by a *, is a <a href="Proper_subset" class="mw-redirect" title="Proper subset">proper subset</a> of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-07" href="https://en.wikipedia.org/wiki/?title=Regular_tree_grammar&oldid=1299311241">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>